Теорема о группе и транспозициях

Группа $S_n$ порождается множеством всех транспозиций.

Возьмем произвольную перестановку $\sigma = (i_1, \ldots, i_n)$ и применим **сортировку пузырьком**. Шаг сортировки переставляет два элемента, что эквивалентно умножению на транспозицию. Результатом сортировки является тождественная перестановка $\Delta = (1, \ldots, n)$. Таким образом, $\Delta = \sigma \circ \tau_1 \circ \ldots \circ \tau_k$, где все $\tau_i$ — транспозиции. Поскольку $\tau_i$ — транспозиция, то $\tau_i^2 = \Delta$, а значит $\tau_i^{-1} = \tau_i$. Умножая равенство $\Delta = \sigma \circ \tau_1 \circ \ldots \circ \tau_k$ на $\tau_k^{-1} \circ \ldots \circ \tau_1^{-1}$ справа и учитывая, что $\Delta$ — тождественный элемент, а $\tau_i^{-1} = \tau_i$, получаем: $$\sigma = \tau_k \circ \ldots \circ \tau_1$$ Следовательно, любая перестановка $\sigma$ может быть представлена как произведение транспозиций. $\square$